#ifndef __LINKLIST_H_
#define __LINKLIST_H_
#include <stddef.h>
using ElementType = int;

class LinkList
{
public:
    // 构造函数
    LinkList();
    // 拷贝构造
    LinkList(const LinkList &list);
    // 析构函数
    ~LinkList();

    // 尾插法
    void InsertTail(const ElementType &element);
    // 头插法
    void InsertHead(const ElementType &element);
    // 中间插入
    void InsertByIndex(int index, const ElementType &element);

    // 按位置删除
    void RemoveByIndex(int index);
    // 按值删除
    void RemoveByElement(const ElementType &element);

    // 按位置修改
    void UpdateByIndex(int index, const ElementType &element);
    // 按值修改
    void UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue);

    // 链表排序
    // 冒泡排序
    void BubbleSort();

    // 归并
    LinkList Merge(const LinkList &list);

    // 排序
    void Sort();

    // 链表逆序
    void Reserve();
    void Reserve2();

    // 显示
    void show();
    // 判断是否是回文结构
    bool IsPalindrome();

private:
    // 节点
    struct Node
    {
        Node(const ElementType &value) : value(value), next(nullptr) {}
        ElementType value; // 数据域
        Node *next;        // 指针域
    };
    // 快速排序
    void FastSort(Node *start, Node *end);
    // 递归排序
    Node *Reserve2(Node *node);

    Node *head;  // 头指针
    size_t size; // 节点个数
};

#endif